<?php
/**
 * User: LRZ
 * Date: 2020/1/13
 * Time: 16:12
 */

/**
 *  219.存在重复元素 II
 *
 *  标签：数组、哈希表
 *
 *  给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的绝对值最大为 k。
 *
 *  示例 1:
 *  输入: nums = [1,2,3,1], k = 3
 *  输出: true
 *
 *  示例 2:
 *  输入: nums = [1,0,1,1], k = 1
 *  输出: true
 *
 *  示例 3:
 *  输入: nums = [1,2,3,1,2,3], k = 2
 *  输出: false
 *
 *  来源：力扣（LeetCode）
 *  链接：https://leetcode-cn.com/problems/contains-duplicate-ii
 *  著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

$start = microtime(true);

$nums = [1, 2, 3, 1];
$k    = 3;
$res  = containsNearbyDuplicate($nums, $k);

$end = microtime(true);
print_r($res);
printf(' total run: %.2f s<br>' . 'memory usage: %.2f M<br> ', $end - $start, memory_get_usage() / 1024 / 1024);

function containsNearbyDuplicate($nums, $k)
{
    $hash = [];
    foreach ($nums as $key => $value) {
        if (isset($hash[$value]) && $key - $hash[$value] <= $k) {
            return true;
        }
        $hash[$value] = $key;
    }
    return false;
}
